package main

import "math/rand"

type Record struct {
	// index int
	detail   []uint64
	fitvalue float64
}

type GAHeap struct {
	data         []Record
	size, curPos int
}

//insert element and maintain the heap structure
func (h *GAHeap) insert(r Record) {
	curIndex, pIndex := h.curPos, (h.curPos - 1) / 2
	for ; curIndex != pIndex && h.data[pIndex].fitvalue > r.fitvalue; curIndex, pIndex = pIndex, (pIndex - 1) / 2 {
		h.data[curIndex] = h.data[pIndex]
	}
	h.data[curIndex] = r
	h.curPos++
	return
}

//check the top record in heap and change the top record if needed
func (h *GAHeap) checkAndExchange(r Record) {

	//do nothing if r already exist
	for _, d := range h.data {
		exist := true
		for i := 0; i < len(r.detail); i++ {
			if r.detail[i] != d.detail[i] {
				exist = false
				break
			}
		}
		if exist {
			// fmt.Println("already exist")
			return
		}
	}

	// fmt.Println(h.curPos)
	if r.fitvalue > h.data[0].fitvalue {
		h.data[0] = r
		h.adjust()
	}
	return
}

//adjust to keep maximized heap
func (h *GAHeap) adjust() {
	pIndex, lChild, rChild := 0, 1, 2
	//iter if parent have child
	for lChild < h.curPos {

		//init incase right child doesn't exist
		var pValue, lValue, rValue float64 = h.data[pIndex].fitvalue, h.data[lChild].fitvalue, 10000000000000
		if rChild < h.curPos {
			rValue = h.data[rChild].fitvalue
		}

		//not need to adjust
		if lValue > pValue && rValue > pValue {
			break
		} else if lValue <= rValue {
			h.data[pIndex], h.data[lChild] = h.data[lChild], h.data[pIndex]
			pIndex = lChild
		} else {
			// fmt.Println(pValue, " ", lValue, " ", rValue)
			// fmt.Println(h.curPos, " ", pIndex, " ", lChild, " ", rChild)
			h.data[pIndex], h.data[rChild] = h.data[rChild], h.data[pIndex]
			pIndex = rChild
		}

		lChild, rChild = (pIndex << 1) + 1, (pIndex + 1) << 1
	}
	return
}

func (h *GAHeap) getAndRemoveTop() (r Record) {
	if h.curPos == 0 {
		panic("heap is empty")
	}
	r, h.data[0] = h.data[0], h.data[h.curPos - 1]
	h.curPos--
	h.adjust()
	return
}

func (h *GAHeap) peekTop() (r Record) {
	if h.curPos == 0 {
		panic("heap is empty")
	}
	r = h.data[0]
	return
}

func (h *GAHeap) randomPair() (father, mother Record) {
	return h.data[rand.Intn(h.size)], h.data[rand.Intn(h.size)]
}
